1. Cache Performance Metrics

• Miss Rate: The percentage of memory accesses not found in the cache. $\text{Miss Rate} = 1 - \text{Hit Rate}$

• Effective Access Time (EAT) for a Two-Level Memory (Cache + Main Memory):

  • Overlapped/Parallel Access (Cache and Main Memory access start simultaneously): $$EAT = H \times Access_C + (1 - H) \times Access_{MM}$$ Where:

    • H = Cache Hit Rate
    • AccessC​ = Cache Access Time
    • AccessMM​ = Main Memory Access Time

  • Non-Overlapped/Sequential Access (Main Memory access starts only after a cache miss):

    $$EAT = H \times Access_C + (1 - H) \times (Access_C + Access_{MM})$$

2. Cache Address Mapping

• General Address Structure: A main memory address is divided into fields to determine its cache location and verify its presence. The total number of bits in the address remains constant.

  $$\text{Total Address Bits} = \text{Tag Bits} + \text{Index Bits (Block or Set)} + \text{Offset Bits}$$

• Field Sizes:

  • Offset Bits: Determined by the block size. If the block size is 2k bytes (or words), the offset field needs k bits.

  • Index Bits (Block or Set):

    • Direct Mapping: Determined by the number of blocks in the cache. If there are 2m blocks in the cache, the Block field needs m bits.

    • Set-Associative Mapping: Determined by the number of sets in the cache. If there are 2s sets, the Set field needs s bits. The number of sets = (Total Cache Blocks) / (N-way Associativity).

  • Tag Bits: The remaining bits after accounting for Index and Offset bits. $$\text{Tag Bits} = \text{Total Address Bits} - \text{Index Bits} - \text{Offset Bits}$$

• Mapping Functions:

  • Direct Mapping: $\text{Cache Block} = (\text{Main Memory Block Number}) \pmod{\text{Number of Cache Blocks}}$

  • Set-Associative Mapping: $\text{Cache Set} = (\text{Main Memory Block Number}) \pmod{\text{Number of Sets}}$

3. Virtual Memory (Paging) Address Translation

• Virtual Address Structure: $\text{Virtual Address} = \text{Virtual Page Number} + \text{Offset}$

  • Offset Bits: Determined by the page size. If the page size is 2k bytes, the offset field needs k bits.

  • Virtual Page Number Bits: $ \text{Total Virtual Address Bits} - \text{Offset Bits} $

• Physical Address Structure: $\text{Physical Address} = \text{Physical Frame Number} + \text{Offset}$

  • Offset Bits: Same as the virtual address offset.
  • Physical Frame Number Bits: Determined by the number of frames in physical memory. If physical memory size is 2p bytes and page size is 2k bytes, the number of frames is 2p−k, requiring p−k bits for the frame number.

• Address Translation (Conceptual): $$\text{Physical Address} = (\text{Frame Number from Page Table using Virtual Page Number}) \text{ concatenated with } (\text{Offset from Virtual Address})$$

4. Virtual Memory Performance

• Effective Access Time (EAT) with Paging (No TLB): $$EAT = (1 - p) \times (Access_{PT} + Access_{MM}) + p \times (\text{Page Fault Service Time})$$

  Since the Page Table (PT) is typically in Main Memory (MM), AccessPT​=AccessMM​. $$EAT = (1 - p) \times (2 \times Access_{MM}) + p \times (\text{Page Fault Service Time})$$

  Where:

  • p = Page Fault Rate
  • AccessMM​ = Main Memory Access Time
  • Page Fault Service Time = Time to handle a page fault (access disk, update page table, etc.)

• Effective Access Time (EAT) with Paging and TLB: (Simplified version assuming page is found in memory after TLB miss)

  $$EAT = t \times (Access_{TLB} + Access_{MM}) + (1 - t) \times (Access_{TLB} + Access_{MM} + Access_{MM})$$$$EAT = t \times (Access_{TLB} + Access_{MM}) + (1 - t) \times (Access_{TLB} + 2 \times Access_{MM})$$

  Where:

  • t = TLB Hit Rate
  • AccessTLB​ = TLB Access Time
  • AccessMM​ = Main Memory Access Time